package org.jieshen.m1.d4;

import java.util.Arrays;

public class Solution {
    //    如果老鼠获胜，则返回 1；
    //    如果猫获胜，则返回 2；
    //    如果平局，则返回 0 。
    int[][] graph;
    int[][][] dp;
    int mouseWin = 1;
    int catWin = 2;
    int draw = 0;
    int n;

    public int catMouseGame(int[][] graph) {
        this.graph = graph;
        this.n = graph.length;
        this.dp = new int[n][n][2];
        // dp数组初始化
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        return getResult(1, 2, 0);
    }

    /**
     * turns %2 = 0，mouse先移动
     * turns %2 = 1，cat先移动
     *
     * @param mouse
     * @param cat
     * @param turns
     * @return
     */
    public int getResult(int mouse, int cat, int turns) {
        if (turns == 2 * n)
            return draw;
        if (dp[mouse][cat][turns % 2] == -1) {
            if (mouse == 0)
                dp[mouse][cat][turns % 2] = mouseWin;
            else if (cat == mouse)
                dp[mouse][cat][turns % 2] = catWin;
            else
                //若双方都没赢，进入下一步
                //因为，仅仅根据mouse和cat的位置无法直接断定此时是和。
                getNextResult(mouse, cat, turns);
        }
        return dp[mouse][cat][turns % 2];
    }

    public void getNextResult(int mouse, int cat, int turns) {
        //判断当前是mouse先动还是cat先动
        //先动的一方，倾向于选择自已获胜的方向
        //cat 不会等于 mouse，因为若cat==mouse，cat就胜利了不需要走下一步
        int curMove = turns % 2 == 0 ? mouse : cat;
        //先假设先走的这一方会失败,若后续会赢或者和，会再更新。若后续没有更新默认值，表示输了。
        int defaultResult = curMove == mouse ? catWin : mouseWin;
        int result = defaultResult;
        for (int next : graph[curMove]) {
            //cat不能去洞口
            if (curMove == cat && next == 0)
                continue;
            int nextMouse = curMove == mouse ? next : mouse;
            int nextCat = curMove == cat ? next : cat;
            int nextResult = getResult(nextMouse, nextCat, turns + 1);
            //有不输的情况
            if (nextResult != defaultResult) {
                result = nextResult;
                //若当前我方能够胜利，则退出循环
                if (result != draw)
                    break;
            }
        }
        dp[mouse][cat][turns % 2] = result;
    }

    public static void main(String[] args) {
//        int[][] graph = {{2, 5}, {3}, {0, 4, 5}, {1, 4, 5}, {2, 3}, {0, 2, 3}};
//        int[][] graph = {{1,3},{0},{3},{0,2}};
        int[][] graph = {{2,6},{2,4,5,6},{0,1,3,5,6},{2},{1,5,6},{1,2,4},{0,1,2,4}};
        int res = new Solution().catMouseGame(graph);
        System.out.println(res);
    }
}
